{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "4khkpduAslqk"
      },
      "source": [
        "# CP-SAT Examples\n",
        "\n",
        "Below you'll find three examples of Google's CP-SAT solver.\n",
        "\n",
        "-   The first example solves a [logic puzzle](#scrollTo=X3kcFue30b_c)\n",
        "-   The second solves a simple [job shop problem](#scrollTo=l_eCCYDE0q7f)\n",
        "-   The third example solves a [two machine scheduling problem with shared\n",
        "    resources](#scrollTo=v6A8SuSe0zTV\u0026line=2\u0026uniqifier=1)\n",
        "    \n",
        "## Runtime and dependencies\n",
        "\n",
        "To run these examples you will need a customization of the default Colab runtime (go/colab) with features and libraries required for the CP-SAT solver (and some visualization tools).\n",
        "\n",
        "To build and run this runtime locally execute the following command at the root of a CitC:\n",
        "\n",
        "```\n",
        "blaze run -c opt ortools/colab:or_notebook -- --logtostderr\n",
        "```\n",
        "\n",
        "Then, click Connect button and click CONNECT under **Local runtime**.\n",
        "\n",
        "Finally, run the following cell to import all necessary dependencies. "
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "_W7FYL570WBA"
      },
      "outputs": [],
      "source": [
        "from ortools.sat.python import cp_model\n",
        "from ortools.sat.colab import visualization"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "X3kcFue30b_c"
      },
      "source": [
        "## Hidato Problem\n",
        "\n",
        "We model the Hidato problem (https://en.wikipedia.org/wiki/Hidato)."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "lYYyoCqbwmj9"
      },
      "outputs": [],
      "source": [
        "def BuildPairs(rows, cols):\n",
        "  \"\"\"Build closeness pairs for consecutive numbers.\n",
        "\n",
        "  Build set of allowed pairs such that two consecutive numbers touch\n",
        "  each other in the grid.\n",
        "\n",
        "  Returns:\n",
        "    A list of pairs for allowed consecutive position of numbers.\n",
        "\n",
        "  Args:\n",
        "    rows: the number of rows in the grid\n",
        "    cols: the number of columns in the grid\n",
        "  \"\"\"\n",
        "  return [(x * cols + y, (x + dx) * cols + (y + dy))\n",
        "          for x in range(rows) for y in range(cols)\n",
        "          for dx in (-1, 0, 1) for dy in (-1, 0, 1)\n",
        "          if (x + dx \u003e= 0 and x + dx \u003c rows and\n",
        "              y + dy \u003e= 0 and y + dy \u003c cols and (dx != 0 or dy != 0))]\n",
        "\n",
        "\n",
        "def BuildPuzzle(problem):\n",
        "  #\n",
        "  # models, a 0 indicates an open cell which number is not yet known.\n",
        "  #\n",
        "  #\n",
        "  puzzle = None\n",
        "  if problem == 1:\n",
        "    # Simple problem\n",
        "    puzzle = [[6, 0, 9],\n",
        "              [0, 2, 8],\n",
        "              [1, 0, 0]]\n",
        "\n",
        "  elif problem == 2:\n",
        "    puzzle = [[0, 44, 41, 0, 0, 0, 0],\n",
        "              [0, 43, 0, 28, 29, 0, 0],\n",
        "              [0, 1, 0, 0, 0, 33, 0],\n",
        "              [0, 2, 25, 4, 34, 0, 36],\n",
        "              [49, 16, 0, 23, 0, 0, 0],\n",
        "              [0, 19, 0, 0, 12, 7, 0],\n",
        "              [0, 0, 0, 14, 0, 0, 0]]\n",
        "\n",
        "  elif problem == 3:\n",
        "    # Problems from the book:\n",
        "    # Gyora Bededek: \"Hidato: 2000 Pure Logic Puzzles\"\n",
        "    # Problem 1 (Practice)\n",
        "    puzzle = [[0, 0, 20, 0, 0],\n",
        "              [0, 0, 0, 16, 18],\n",
        "              [22, 0, 15, 0, 0],\n",
        "              [23, 0, 1, 14, 11],\n",
        "              [0, 25, 0, 0, 12]]\n",
        "\n",
        "  elif problem == 4:\n",
        "    # problem 2 (Practice)\n",
        "    puzzle = [[0, 0, 0, 0, 14],\n",
        "              [0, 18, 12, 0, 0],\n",
        "              [0, 0, 17, 4, 5],\n",
        "              [0, 0, 7, 0, 0],\n",
        "              [9, 8, 25, 1, 0]]\n",
        "\n",
        "  elif problem == 5:\n",
        "    # problem 3 (Beginner)\n",
        "    puzzle = [[0, 26, 0, 0, 0, 18],\n",
        "              [0, 0, 27, 0, 0, 19],\n",
        "              [31, 23, 0, 0, 14, 0],\n",
        "              [0, 33, 8, 0, 15, 1],\n",
        "              [0, 0, 0, 5, 0, 0],\n",
        "              [35, 36, 0, 10, 0, 0]]\n",
        "  elif problem == 6:\n",
        "    # Problem 15 (Intermediate)\n",
        "    puzzle = [[64, 0, 0, 0, 0, 0, 0, 0],\n",
        "              [1, 63, 0, 59, 15, 57, 53, 0],\n",
        "              [0, 4, 0, 14, 0, 0, 0, 0],\n",
        "              [3, 0, 11, 0, 20, 19, 0, 50],\n",
        "              [0, 0, 0, 0, 22, 0, 48, 40],\n",
        "              [9, 0, 0, 32, 23, 0, 0, 41],\n",
        "              [27, 0, 0, 0, 36, 0, 46, 0],\n",
        "              [28, 30, 0, 35, 0, 0, 0, 0]]\n",
        "  return puzzle\n",
        "\n",
        "\n",
        "def SolveHidato(puzzle, index):\n",
        "  \"\"\"Solve the given hidato table.\"\"\"\n",
        "  # Create the model.\n",
        "  model = cp_model.CpModel()\n",
        "\n",
        "  r = len(puzzle)\n",
        "  c = len(puzzle[0])\n",
        "\n",
        "  #\n",
        "  # declare variables\n",
        "  #\n",
        "  positions = [model.NewIntVar(0, r * c - 1, 'p[%i]' % i)\n",
        "               for i in range(r * c)]\n",
        "\n",
        "  #\n",
        "  # constraints\n",
        "  #\n",
        "  model.AddAllDifferent(positions)\n",
        "\n",
        "  #\n",
        "  # Fill in the clues\n",
        "  #\n",
        "  for i in range(r):\n",
        "    for j in range(c):\n",
        "      if puzzle[i][j] \u003e 0:\n",
        "        model.Add(positions[puzzle[i][j] - 1] == i * c + j)\n",
        "\n",
        "  # Consecutive numbers must touch each other in the grid.\n",
        "  # We use an allowed assignment constraint to model it.\n",
        "  close_tuples = BuildPairs(r, c)\n",
        "  for k in range(0, r * c - 1):\n",
        "    model.AddAllowedAssignments([positions[k], positions[k + 1]], close_tuples)\n",
        "\n",
        "  #\n",
        "  # solution and search\n",
        "  #\n",
        "\n",
        "  solver = cp_model.CpSolver()\n",
        "  solver.parameters.log_search_progress = True\n",
        "  status = solver.Solve(model)\n",
        "\n",
        "  if status == cp_model.FEASIBLE or status == cp_model.OPTIMAL:\n",
        "    output = visualization.SvgWrapper(10, r, 40.0)\n",
        "    for i in range(len(positions)):\n",
        "      val = solver.Value(positions[i])\n",
        "      x = val % c\n",
        "      y = val // c\n",
        "      color = 'white' if puzzle[y][x] == 0 else 'lightgreen'\n",
        "      value = solver.Value(positions[i])\n",
        "      output.AddRectangle(x, r - y - 1, 1, 1, color, 'black', str(i + 1))\n",
        "\n",
        "    output.AddTitle('Puzzle %i solved in %f s' % (index, solver.WallTime()))\n",
        "    output.Display()\n",
        "\n",
        "\n",
        "for i in range(1, 7):\n",
        "  SolveHidato(BuildPuzzle(i), i)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "l_eCCYDE0q7f"
      },
      "source": [
        "## Jobshop example\n",
        "\n",
        "This example demonstrates jobshop scheduling\n",
        "(https://en.wikipedia.org/wiki/Job_shop_scheduling)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "aBGOY3xWgV-g"
      },
      "outputs": [],
      "source": [
        "def JobshopFT06():\n",
        "  \"\"\"Solves the ft06 jobshop from the jssp library.\n",
        "  (http://people.brunel.ac.uk/~mastjjb/jeb/orlib/jobshopinfo.html).\"\"\"\n",
        "\n",
        "  # Creates the solver.\n",
        "  model = cp_model.CpModel()\n",
        "\n",
        "  machines_count = 6\n",
        "  jobs_count = 6\n",
        "  all_machines = range(0, machines_count)\n",
        "  all_jobs = range(0, jobs_count)\n",
        "\n",
        "  durations = [[1, 3, 6, 7, 3, 6],\n",
        "               [8, 5, 10, 10, 10, 4],\n",
        "               [5, 4, 8, 9, 1, 7],\n",
        "               [5, 5, 5, 3, 8, 9],\n",
        "               [9, 3, 5, 4, 3, 1],\n",
        "               [3, 3, 9, 10, 4, 1]]\n",
        "\n",
        "  machines = [[2, 0, 1, 3, 5, 4],\n",
        "              [1, 2, 4, 5, 0, 3],\n",
        "              [2, 3, 5, 0, 1, 4],\n",
        "              [1, 0, 2, 3, 4, 5],\n",
        "              [2, 1, 4, 5, 0, 3],\n",
        "              [1, 3, 5, 0, 4, 2]]\n",
        "\n",
        "  # Computes horizon dynamically.\n",
        "  horizon = sum([sum(durations[i]) for i in all_jobs])\n",
        "\n",
        "  # Creates jobs.\n",
        "  all_tasks = {}\n",
        "  for i in all_jobs:\n",
        "    for j in all_machines:\n",
        "      start = model.NewIntVar(0, horizon, 'start_%i_%i' % (i, j))\n",
        "      duration = durations[i][j]\n",
        "      end = model.NewIntVar(0, horizon, 'end_%i_%i' % (i, j))\n",
        "      interval = model.NewIntervalVar(start, duration, end,\n",
        "                                      'interval_%i_%i' % (i, j))\n",
        "      all_tasks[(i, j)] = (start, end, interval)\n",
        "\n",
        "  # Create disjunctive constraints.\n",
        "  for i in all_machines:\n",
        "    machines_jobs = []\n",
        "    for j in all_jobs:\n",
        "      for k in all_machines:\n",
        "        if machines[j][k] == i:\n",
        "          machines_jobs.append(all_tasks[(j, k)][2])\n",
        "    model.AddNoOverlap(machines_jobs)\n",
        "\n",
        "  # Makespan objective: minimize the total length of the schedule.\n",
        "  obj_var = model.NewIntVar(0, horizon, 'makespan')\n",
        "  model.AddMaxEquality(\n",
        "      obj_var, [all_tasks[(i, machines_count - 1)][1] for i in all_jobs])\n",
        "  model.Minimize(obj_var)\n",
        "\n",
        "  # Precedences inside a job.\n",
        "  for i in all_jobs:\n",
        "    for j in range(0, machines_count - 1):\n",
        "      model.Add(all_tasks[(i, j + 1)][0] \u003e= all_tasks[(i, j)][1])\n",
        "\n",
        "  solver = cp_model.CpSolver()\n",
        "  solver.parameters.log_search_progress = True\n",
        "  response = solver.Solve(model)\n",
        "  starts = [[solver.Value(all_tasks[(i, j)][0]) for j in all_machines]\n",
        "            for i in all_jobs]\n",
        "  visualization.DisplayJobshop(starts, durations, machines, 'FT06')\n",
        "\n",
        "\n",
        "JobshopFT06()"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "v6A8SuSe0zTV"
      },
      "source": [
        "## Two Machine Scheduling\n",
        "\n",
        "We have a set of jobs to perform (duration, width). We have two parallel\n",
        "machines that can perform this job. One machine can only perform one job at a\n",
        "time. At any point in time, the sum of the width of the two active jobs cannot\n",
        "exceed a max_width.\n",
        "\n",
        "The objective is to minimize the max end time of all jobs."
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "aJ4tCfc4z8DU"
      },
      "outputs": [],
      "source": [
        "def TwoMachineScheduling():\n",
        "  model = cp_model.CpModel()\n",
        "\n",
        "  jobs = [[3, 3],  # (duration, width)\n",
        "          [2, 5],\n",
        "          [1, 3],\n",
        "          [3, 7],\n",
        "          [7, 3],\n",
        "          [2, 2],\n",
        "          [2, 2],\n",
        "          [5, 5],\n",
        "          [10, 2],\n",
        "          [4, 3],\n",
        "          [2, 6],\n",
        "          [1, 2],\n",
        "          [6, 8],\n",
        "          [4, 5],\n",
        "          [3, 7]]\n",
        "\n",
        "  max_width = 10\n",
        "\n",
        "  horizon = sum(t[0] for t in jobs)\n",
        "  num_jobs = len(jobs)\n",
        "  all_jobs = range(num_jobs)\n",
        "\n",
        "  intervals = []\n",
        "  intervals0 = []\n",
        "  intervals1 = []\n",
        "  performed = []\n",
        "  starts = []\n",
        "  ends = []\n",
        "  demands = []\n",
        "\n",
        "  for i in all_jobs:\n",
        "    # Create main interval (to be used in the cumulative constraint).\n",
        "    start = model.NewIntVar(0, horizon, 'start_%i' % i)\n",
        "    duration = jobs[i][0]\n",
        "    end = model.NewIntVar(0, horizon, 'end_%i' % i)\n",
        "    interval = model.NewIntervalVar(start, duration, end, 'interval_%i' % i)\n",
        "    starts.append(start)\n",
        "    intervals.append(interval)\n",
        "    ends.append(end)\n",
        "    demands.append(jobs[i][1])\n",
        "\n",
        "    performed_on_m0 = model.NewBoolVar('perform_%i_on_m0' % i)\n",
        "    performed.append(performed_on_m0)\n",
        "\n",
        "    # Create an optional copy of interval to be executed on machine 0.\n",
        "    start0 = model.NewIntVar(\n",
        "        0, horizon, 'start_%i_on_m0' % i)\n",
        "    end0 = model.NewIntVar(\n",
        "        0, horizon, 'end_%i_on_m0' % i)\n",
        "    interval0 = model.NewOptionalIntervalVar(\n",
        "        start0, duration, end0, performed_on_m0, 'interval_%i_on_m0' % i)\n",
        "    intervals0.append(interval0)\n",
        "\n",
        "    # Create an optional copy of interval to be executed on machine 1.\n",
        "    start1 = model.NewIntVar(\n",
        "        0, horizon, 'start_%i_on_m1' % i)\n",
        "    end1 = model.NewIntVar(\n",
        "        0, horizon, 'end_%i_on_m1' % i)\n",
        "    interval1 = model.NewOptionalIntervalVar(\n",
        "        start1, duration, end1, performed_on_m0.Not(), 'interval_%i_on_m1' % i)\n",
        "    intervals1.append(interval1)\n",
        "\n",
        "    # We only propagate the constraint if the task is performed on the machine.\n",
        "    model.Add(start0 == start).OnlyEnforceIf(performed_on_m0)\n",
        "    model.Add(start1 == start).OnlyEnforceIf(performed_on_m0.Not())\n",
        "\n",
        "  # Max width constraint (modeled as a cumulative).\n",
        "  model.AddCumulative(intervals, demands, max_width)\n",
        "\n",
        "  # Choose which machine to perform the jobs on.\n",
        "  model.AddNoOverlap(intervals0)\n",
        "  model.AddNoOverlap(intervals1)\n",
        "\n",
        "  # Objective variable.\n",
        "  makespan = model.NewIntVar(0, horizon, 'makespan')\n",
        "  model.AddMaxEquality(makespan, ends)\n",
        "  model.Minimize(makespan)\n",
        "\n",
        "  # Symmetry breaking.\n",
        "  model.Add(performed[0] == 0)\n",
        "\n",
        "  # Solve model.\n",
        "  solver = cp_model.CpSolver()\n",
        "  solver.parameters.log_search_progress = True\n",
        "  solver.Solve(model)\n",
        "\n",
        "  # Output solution.\n",
        "  output = visualization.SvgWrapper(solver.ObjectiveValue(), max_width, 40.0)\n",
        "  output.AddTitle('Makespan = %i' % solver.ObjectiveValue())\n",
        "  color_manager = visualization.ColorManager()\n",
        "  color_manager.SeedRandomColor(0)\n",
        "  for i in all_jobs:\n",
        "    performed_machine = 1 - solver.Value(performed[i])\n",
        "    start = solver.Value(starts[i])\n",
        "    dx = jobs[i][0]\n",
        "    dy = jobs[i][1]\n",
        "    sy = performed_machine * (max_width - dy)\n",
        "    output.AddRectangle(start, sy, dx, dy, color_manager.RandomColor(), 'black',\n",
        "                        'j%i' % i)\n",
        "\n",
        "  output.AddXScale()\n",
        "  output.AddYScale()\n",
        "  output.Display()\n",
        "\n",
        "\n",
        "TwoMachineScheduling()"
      ]
    }
  ],
  "metadata": {
    "colab": {
      "collapsed_sections": [],
      "last_runtime": {
        "build_target": "",
        "kind": "local"
      },
      "name": "cp-sat1.ipynb",
      "provenance": [
        {
          "file_id": "1yJJLir0ITXD8I-SyJ06ZdN1x12fEsTlv",
          "timestamp": 1571253284638
        }
      ],
      "toc_visible": true
    },
    "kernelspec": {
      "display_name": "Python 3",
      "name": "python3"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 0
}
